Repeated string match [Rabin-Karp Algorithm (rolling hash)]

Time: O(N + M); Space: O(1); easy

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

Example 1:

Input: A = “abcd”, B = “cdabcdab”

Output: 3

Explanation:

  • Because by repeating A three times (“abcdabcdabcd”), B is a substring of it;

  • and B is not a substring of A repeated two times (“abcdabcd”).

Example 2:

Input: A = “a”, B = “b”

Output: -1

Constraints:

  • The length of A and B will be between 1 and 10000.

[1]:

class Solution1(object):
    """
    Rabin-Karp Algorithm (rolling hash)
    """
    def repeatedStringMatch(self, A, B):
        """
        :type A: str
        :type B: str
        :rtype: int
        """
        def check(index):
            return all(A[(i+index) % len(A)] == c
                       for i, c in enumerate(B))

        M, p = 10**9+7, 113
        p_inv = pow(p, M-2, M)
        q = (len(B)+len(A)-1) // len(A)

        b_hash, power = 0, 1
        for c in B:
            b_hash += power * ord(c)
            b_hash %= M
            power = (power*p) % M

        a_hash, power = 0, 1
        for i in range(len(B)):
            a_hash += power * ord(A[i%len(A)])
            a_hash %= M
            power = (power*p) % M

        if a_hash == b_hash and check(0): return q

        power = (power*p_inv) % M
        for i in range(len(B), (q+1)*len(A)):
            a_hash = (a_hash-ord(A[(i-len(B))%len(A)])) * p_inv
            a_hash += power * ord(A[i%len(A)])
            a_hash %= M
            if a_hash == b_hash and check(i-len(B)+1):
                return q if i < q*len(A) else q+1

        return -1


[2]:

s = Solution1()

A = "abcd"
B = "cdabcdab"
assert s.repeatedStringMatch(A, B) == 3

A = "a"
B = "b"
assert s.repeatedStringMatch(A, B) == -1